# define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* reverseList(struct ListNode* head) {


    struct ListNode* cur = NULL;
    struct ListNode* prev = NULL;
    while (head != NULL)
    {
        cur = head->next;
        head->next = prev;
        prev = head;
        head = cur;
    }

    return prev;
}

struct ListNode* middleNode1(struct ListNode* head) {
    struct ListNode* prev = head;
    struct ListNode* cur = head;
    while (cur->next != NULL)
    {
        prev = prev->next;
        cur = cur->next;
        if (cur->next != NULL)
        {
            cur = cur->next;
        }
        else
        {
            break;
        }

    }
    return prev;
}

struct ListNode* middleNode2(struct ListNode* head) {
    struct ListNode* prev = head;
    struct ListNode* cur = head;
    while (cur != NULL && cur->next != NULL)
    {
        prev = prev->next;
        cur = cur->next->next;
    }
    return prev;
}


int kthToLast(struct ListNode* head, int k) {
    struct ListNode* tail = head;
    while (tail != NULL)
    {
        tail = tail->next;
    }
    int n = 0;
    struct ListNode* prev = head;
    while (n != k)
    {
        prev = head;
        while (prev->next != tail)
        {
            prev = prev->next;
        }
        n++;
        tail = prev;
    }
    return  tail->val;
}


int kthToLast(struct ListNode* head, int k) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (k--)
    {
        fast = fast->next;
    }

    while (fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow->val;
}


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL)
    {
        return list2;
    }
    else if (list2 == NULL)
    {
        return list1;
    }
    struct ListNode* prev1 = list1;
    struct ListNode* prev2 = list2;
    struct ListNode* head = NULL;
    if (prev1->val <= prev2->val)
    {
        head = prev1;
        prev1 = prev1->next;
    }
    else
    {
        head = prev2;
        prev2 = prev2->next;
    }
    struct ListNode* tail = head;
    while (prev1 != NULL || prev2 != NULL)
    {
        if (prev1 == NULL)
        {
            tail->next = prev2;
            prev2 = prev2->next;
        }
        else if (prev2 == NULL)
        {
            tail->next = prev1;
            prev1 = prev1->next;
        }
        else
        {
            if (prev1->val <= prev2->val)
            {
                tail->next = prev1;
                prev1 = prev1->next;
            }
            else
            {
                tail->next = prev2;
                prev2 = prev2->next;
            }
        }
        tail = tail->next;
    }
    return head;
}